This invention relates to a transfer system, and more particularly to a system which selects the location in high speed, low capacity working store into which a block of information from a low speed large capacity backup store is to be located.
When a situation exists where there is a set having a fixed number of members, a problem arises as to which member to replace when the set is full and it is desired to add a new member. This invention provides an economical solution to the replacement problem when the members of the set are being utilized in a manner involving a higher probability of re-use of recently utilized blocks of information and applies the solution to a specific problem arising with respect to the memory system of a large data processing system.
Various techniques are known whereby several computer programs, executed either by a single central processing unit or by a plurality of processing units, share one memory. A memory being shared by programs in this manner requires an extremely large storage capacity, a capacity which is often larger than its actual capacity of the immediately associated compatible store. To accommodate this situation, the concept of "virtual storage" is employed. This virtual storage is divided into segments or blocks. Each block or segment may include several pages which may be located randomly throughout main storage and swapped in and out as they are needed.
In an electronic computer, it is desirable to store all information in such a manner that it be immediately available for control and processing. To achieve the fastest processing, the best storage apparatus would be one having a capacity at least as large as required for handling the largest possible problem and the highest possible speed. However, because high speed memory is expensive, other alternatives to a very large high speed memory have been proposed. One economical and workable solution to the problem involves the use of a large capacity, low speed store, which has sufficient capacity to store all the information required for any desired problem. A low capacity, high speed store is also provided and all programs are written as if all the information were in a high speed store having the extensive capacity of the entire low speed store. The entire system of page transfers and replacement is thereby rendered "transparent" to the programmer.
As part of the transfer, or replacement system for such a virtual memory storage arrangement, a third "associative memory" is provided to indicate which low speed stored data is also contained in the high speed store at any given time. When a given program running on the computer requires a particular word of information, a check is made to see if this word is in the high speed store. If it is in the high speed store, the information is immediately retrieved and used. If the word is not in the high speed store, the required word is transferred from the low speed backup store to the high speed store. It has been found impractical to make this exchange on a single word basis in the course of sequential execution of the various instructions of a given program, due to the slow speed of the backup store. The time delay involved in making the transfer has been found to be almost independent of whether a single word or a block of words is transferred. Further, experience has shown that the probability is high that if one word is required, others in its locality will also be needed during the course of the execution of instructions of the requesting or bidding program. Therefore, when a determination is made that a word of information is required from backup store, a transfer of the block containing this word is made from the backup store into the high speed store.
The mechanization of low speed to high speed core transfer of blocks of data described in the previous paragraph is only effective for so long as there are empty blocks of addresses in high speed store. When the high speed store is full, a replacement problem arises. When replacement of an information block is required, an ideal replacement criteria would always cause the block of information which is not going to be used again for the longest period of time to be replaced. Unfortunately, an actual determination according to this criteria during the course of execution of competing or bidding is unduly time consuming and thus impractical. Existing systems, which have either selected the block to be replaced randomly or have made the selection on a first-in, first-out (FIFO) basis, have fallen far short of the ideal.
More recently there have evolved alternatives to a first-in, first-out algorithm implementation such as those taking into account the relative utilization of the members of a fixed length set. Relative utilization criteria ideally involve dynamically ordering the blocks of information (i.e. members of the set) according to the sequence of references to them, and when the necessity arises to replace a block, replacing the block to which reference has not been made for the longest period of time. This system utilizes the empirically determined fact that the blocks of information which have been most recently referred to are most likely to be referenced in the near future. Although it is known that implementation of replacement systems subject to these criteria provides good results on a wide variety of replacement or relocation problems, it has been determined that full and rigorous implementation of this criteria is a relatively costly procedure involving extensive additional electronic equipment.
An alternative to dynamic reordering is included in the system of U.S. Pat. No. 3,541,529 issued to Robert A. Nelson, et al. which discloses marking each block as it is utilized or altered and selecting for replacement only unmarked blocks. When the set of unmarked blocks vanishes, a mechanism is provided for unmarking all the blocks or all but the last block and then proceeding as before.
Another heuristic approach to storage paging is that described in both "Automatic Heuristic Storage Paging Mechanism" by M. I. Davis, IBM Technical Disclosure Bulletin, Volume 16, No. 1 June 1973. A heuristically adaptive address translator control storage arrangement is provided which is transparent to software so that virtual storage operations are effected with induced software overhead loading. By "heuristically adaptive" is meant alterable activity indicator set each time a given page is accessed. A heuristically decaying activity plot is maintained within the address translator.
In general, therefore, the prior art has disclosed systems which either (1) maintain detailed historical information, at great expense, to provide a rigorous "least recently used" replacement formula, or (2) are subject at least at some time to replacing a block of data which has very recently been accessed (and is likely to be needed soon), at a considerable cost, on the average, of computer time.
A principal object of the present invention, therefore, is to entirely preclude replacement of at least the 50% of the information blocks or pages which have been most recently used and concurrently avoid significant increases in hardware or data processing costs.